Parsing and pattern-matching are important functions for many different applications, including compilers for programming languages, security, e.g., intrusion detection, virus scanning, etc., and data compression.
As is known in the art, parsing and pattern-matching typically involves testing an input document, in the form of an input stream of characters, to see if it meets or matches one or more conditions. Examples of such conditions include testing if a character is part of a reserved word or variable or attribute name, if the character obeys any defined naming conventions, e.g., what characters are allowed to be part of such a name, and/or if the character string obeys the relevant syntax rules, etc. The latter may also include checking the character string against certain document state information, such as, for example, testing a new variable name against a list of all previously processed variable names to determine if the new variable name is unique. Another example would be to test if a value assigned to a variable is in accordance with the type declaration of that variable.
These functions are typically implemented in software. However, the Applicants have recognized that the parsing and pattern-matching performance of existing, conventional software implementations can be limited, e.g., due to the way in which the processors implementing the software tend to operate.
Furthermore, newer applications that require parsing and pattern-matching functions that impose significantly higher processing throughput requirements regarding, e.g., the number of characters and/or documents that need to be parsed and/or searched for patterns per unit time, and/or that require significantly reduced latency in the parsing/pattern-matching process are becoming more commonplace.
An example of such applications is emerging applications based on the Extensible Markup Language (XML), which provides, as is known in the art, a standard format to exchange electronic documents. These applications of XML include web-pages, data storage and retrieval, communications protocols, e.g., XML-RPC and SOAP, object serialization, etc. These applications have in common that they require a high-performance parser function for processing the XML-based information.
The Applicants believe therefore that there will increasingly become a need for more efficient parsing and pattern-matching systems.